import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;

public class PrimeNumbers {
	
		public static void main (String[] args) throws IOException {
			
			BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
			System.out.println("Enter the number: ");
			int num = Integer.parseInt(reader.readLine());
			System.out.println("Prime numbers up to "+num+": ");	
			int N=num;
		
				boolean[] isPrime = new boolean[N+1];
 				Arrays.fill(isPrime, 2, N+1, true);	
				isPrime[1] = false;
 				
				for (int i=2; i*i <= N; i++)	{
					if (isPrime[i])	{				
						for (int k=i*i; k<=N; k+=i)	{
							isPrime[k]= false;
						}	
					}
				}
			
			ArrayList<Integer> primes = new ArrayList<Integer>();
			for (int z=0; z<=N; z++)	{
			 	if (isPrime[z])	{
			 		primes.add(z);
			 	}
			}
			
		System.out.println(primes);	
		
		}
			
}
